In 1998, Blaze et al. proposed a technique referred to as proxy re-encryption in connection with a public key encryption system.
A basic model for this technique comprises five functions (hereinafter also referred to as algorithms) for key generation, encryption, decryption, re-encryption key generation, and re-encryption. The functions of key generation, encryption, and decryption are similar to the corresponding functions for normal public key encryption.
(Key generation) KeyGen (1k)→(pk, sk)
The key generation algorithm KeyGen outputs a set of a public key pk and a private key (pk, sk) in response to input of a security parameter of 1k.
(Encryption) Enc (pkA, m)→CA 
The encryption algorithm Enc outputs an encrypted data CA destined for a user A in response to input of a public key pkA and a message m of a user A.
(Decryption) Dec (skA, CA)→m
The decryption algorithm Dec outputs the message m in response to input of the private key skA of the user A and the encrypted data CA destined for the user A.
(Re-encryption key generation) ReKeyGen (pkA, skA, pkB, skB)→rkA→B 
The re-encryption key generation algorithm ReKeyGen outputs a re-encryption key rkA→B in response to input of the public key pkA of the user A, the private key skA of the user A, a public key pkB of a user B, and a private key skA of the user B.
(Re-encryption) ReEnc (rkA→B, CA)
The re-encryption algorithm ReEnc outputs an encrypted data CB in response to input of the re-encryption key rkA→B and the encrypted data CA destined for the user A.
The basic model has been described. However, the following models have been designed depending on an implementation scheme for re-encryption: a model with inputs to the functions different from the above-described inputs, and a model with functions and keys different from the above-described functions and keys.
For example, in connection with inputs to the re-encryption key generation algorithm, the following models have been designed: a model referred to as a non-interactive model and eliminating the need for the input of the private key skB of the user B, and a model involving input of the re-encryption key rkA→B destined for the user B and a private key skC of a user C instead of the private key skA of the user A.
The following models are also known: a model referred to as a unidirectional model and allowing re-encryption CA→CB to be achieved using the re-encryption key rkA→B, while unable to carry out the reverse conversion of the encrypted data CB→CA, and a model referred to as a bidirectional model and allowing the reverse conversion to also be achieved. In the bidirectional model, the re-encryption key rkA→B may be represented as rkAB.
Moreover, a scheme based on ID based encryption, a type of public key encryption, has also been designed. This scheme increases the number of function setups for generation of a master key and adds a master key and an ID as inputs to the key generation algorithm KeyGen. In the ID based encryption, the public key pk is the ID itself.
As examples of specific schemes, the following are known: for the unidirectional model, schemes described in G. Ateniese, K. Fu, M. Green, S. Hohenberger. Improved Proxy Re-Encryption Schemes with Applications to Secure Distributed Storage. In NDSS '05, 2005, and B. Libert, D. Vergnaud. Tracing Malicious Proxies in Proxy Re-Encryption. In Pairing 2008, 2008, for the bidirectional model, a scheme described in R. Canetti, S. Hohenberger. Chosen-Ciphertext Secure Proxy Re-Encryption. In ACM CCS '07, 2005, and for the ID based encryption, schemes described in M. Green, G. Ateniese. Identity-Based Proxy Re-encryption. In ACNS '07, 2007, and T. Matsuo. Proxy Re-encryption Systems for Identity-based Encryption. In Pairing 2007, 2007. The embodiments are based on a scheme described in Benoit Libert, Damien Vergnaud, “Unidirectional Chosen-Ciphertext Secure Proxy Re-encryption”, Public Key Cryptography 2008, pp. 360-279 (hereinafter, referred to as Non-Patent Literature 8)
FIG. 9 is a schematic diagram showing an example of a content distribution system illustrating a re-encryption technique such as described above. The content distribution system comprises three entities including a content provider 1, a distribution system 2, and a user 3. The user 3 is referred to as user A or user B when the users are distinguished from one another.
In prior arrangement, the content provider 1 is assumed to have a public key pkGr of the distribution system 2. The distribution system 2 is assumed to have re-encryption keys rkGr→A and rkGr→B used to re-encrypt an encrypted data (pkGr, M) destined for the distribution system 2 into an encrypted data destined for a particular user A's re-encrypted data E(pkA, M) or B's re-encrypted data E(pkB, M). Each user 3 is assumed to have a private key skA or skB used to decrypt the re-encrypted data E destined for the user 3's encrypted data E(pkA, M) or E(pkB, M). Various other keys and parameters will not be described.
Next, the content provider 1 encrypts a data M using the public key pkGr of the distribution system 2 and distributes the resultant encrypted data E (pkGr, M) to the distribution system 2.
The distribution system 2 receives the encrypted data E (pkGr, M) from the content provider 1. Subsequently, in response to a content request received from, for example, the user A, the distribution system 2 re-encrypts the encrypted data E (pkGr, M) into a re-encrypted data destined for the particular user A's encrypted data E(pkA, M) based on the re-encryption key for the particular user A rkGr→A. The distribution system 2 distributes the resultant re-encrypted data E(pkA, M) to the user A.
The user A decrypts the re-encrypted data E(pkA, M) received from any distribution system 2 using the private key skA, and utilizes the resultant data M.
In the content distribution system as described above, the data M is subjected to no single decryption during a period from the encryption performed by the content provider 1 until the decryption performed by the user A. This enables possible information leakage to be inhibited during a process of content distribution.
Furthermore, the content provider 1 performs encryption using the public key pkGr of the distribution system 2 without identifying the user 3. Thus, only the public key pkGr of the distribution system 2 needs to be managed, enabling a reduction in the cost of key management.
The distribution system 2 re-encrypts the encrypted data E(pkGr, M) for the user 3 without decrypting the encrypted data E(pkGr, M). This eliminates the need to strictly manage a server used for re-encryption, enabling a reduction in costs.
The user 3 can utilize any data M as in the case of the conventional art simply by issuing a content request to the distribution system 2.
The re-encryption technique as described above normally has no particular problem, but through their research the inventors have found the following disadvantages.
The conventional encryption system comprises two entities, an encrypting person and a decrypting person and has only to be able to identify the decrypting person. In contrast, according to the re-encryption technique, a decrypting person disadvantageously fails to verify for whom encrypted data that has been re-encrypted is originally destined if the decrypting person does not know from whom the decrypting person receives re-encrypted data.
For example, according to the re-encryption technique, a function to generate a re-encryption key can be separated from a function to perform re-encryption, and thus, these functions may be implemented in separate entities. In this case, even when receiving re-encrypted data from an entity that has performed re-encryption, the decrypting user has no means for verifying for whom encrypted data that has been re-encrypted is originally destined.
Therefore, even if a user or a third person who investigates the cause of leakage receives leaked encrypted data that has been re-encrypted, the user or the third person is unable to verify, in this state, for whom the encrypted data that has been re-encrypted is originally destined. Thus, identifying the source of leakage is difficult.
As a candidate for a technique for eliminating the above-described disadvantage, for example, proxy re-signature is known. However, the technique is configured to replace a signature and thus needs to implement a combination of proxy re-signature with proxy re-encryption that achieves the above-described re-encryption function. However, the combination is difficult to realize because the combination involves an increased amount of calculation and an increased data length needed to achieve both functions, and because no suitable method for allowing both systems to cooperate with each other is known.
As another candidate for a technique for eliminating the disadvantage, a technique for combining proxy re-encryption with an existing electronic signature system has been proposed. However, for this technique, it is presently unknown to which data and how the encrypting person and the re-encrypting person may add electronic signatures. Thus, implementing the technique is difficult.
That is, for the re-encryption technique, the above-described disadvantages have not been eliminated.
An object of the embodiments disclosed herein is to provide a re-encrypted data verification program, a re-encryption apparatus, and a re-encryption system wherein a decryption apparatus, upon receiving re-encrypted data, can verify for whom encrypted data that has been re-encrypted is originally destined.
Thus, a case will be described herein where a function to generate a re-encryption key and a function to perform re-encryption are executed by different entities.